package org.example.alig;

import java.util.Stack;

public class Alig7 {
    public static void main(String[] args) {
        int arr[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        long x = System.nanoTime();
        int res = getRain3(arr);
        long y = System.nanoTime() - x;
        System.out.println(res);
        System.out.println(y);
    }

    private static int getRain(int arr[]) {
        /**
         * def trap(self, height):
         *         res, hei_len = 0, len(height)
         *         for i in range(1, hei_len-1):
         *             max_left, max_right = 0, 0
         *             for l in range(i+1):
         *                 max_left = max(max_left, height[l])
         *             for r in range(i, hei_len):
         *                 max_right = max(max_right, height[r])
         *             res += min(max_left, max_right) - height[i]
         *         return res
         */
        int res = 0;
        int len = arr.length;
        for (int i = 1; i < len - 1; i++) {
            int left = 0, right = 0;
            for (int l = 0; l < i + 1; l++) {
                left = Math.max(left, arr[l]);
            }
            for (int r = i; r < len; r++) {
                right = Math.max(right, arr[r]);
            }
            res += (Math.min(left, right) - arr[i]);
        }
        return res;
    }

    private static int getRain2(int arr[]) {
        /**
         * def trap(self, height):
         *         res, hei_len, peak = 0, len(height), 0
         *         if hei_len < 3:
         *             return 0
         *         max_val = height[0]
         *         for i in range(1, hei_len):
         *             if height[i] >= max_val:
         *                 max_val = height[i]
         *                 peak = i
         *
         *         max_left, max_right = height[0], height[-1]
         *         for i in range(peak):
         *             if max_left < height[i]:
         *                 max_left = height[i]
         *             else:
         *                 res += max_left - height[i]
         *
         *         for i in range(hei_len-1, peak, -1):
         *             if max_right < height[i]:
         *                 max_right = height[i]
         *             else:
         *                 res += max_right - height[i]
         *         return res
         */
        int res = 0;
        int len = arr.length;
        if (len < 3) return 0;
        int maxValue = arr[0], maxIndex = 0;

        for (int i = 1; i < len; i++) {
            if (arr[i] > maxValue) {
                maxValue = arr[i];
                maxIndex = i;
            }
        }
        int maxLeft = arr[0];
        for (int i = 0; i < maxIndex; i++) {
            if (maxLeft < arr[i])
                maxLeft = arr[i];
            else
                res += maxLeft - arr[i];
        }

        int maxRight = arr[len - 1];
        for (int i = len - 1; i > maxIndex; i--) {
            if (maxRight < arr[i])
                maxRight = arr[i];
            else
                res += maxRight - arr[i];
        }
        return res;
    }
    // @formatter:off
    /**
     *         left, right = 0, len(height) - 1
     *         left_max, right_max = 0, 0
     *         res = 0
     *         while left < right:
     *             if height[left] < height[right]:
     *                 if height[left] >= left_max:
     *                     left_max = height[left]
     *                 else:
     *                     res += left_max - height[left]
     *                 left += 1
     *             else:
     *                 if height[right] >= right_max:
     *                     right_max = height[right]
     *                 else:
     *                     res += right_max - height[right]
     *                 right -= 1
     */
    // @formatter:on
    private static int getRain3(int arr[]) {
        int len = arr.length;
        int left = 0, right = len - 1, res = 0;
        int maxLeft = 0, maxRight = 0;
        while (left < right) {
            if (arr[left] < arr[right]) {
                if (arr[left] >= maxLeft)
                    maxLeft = arr[left];
                else
                    res += maxLeft - arr[left];
                left++;
            } else {
                if (arr[right] >= maxRight)
                    maxRight = arr[right];
                else
                    res += maxRight - arr[right];
                right--;
            }
        }
        return res;
    }

    private static int getRain4(int arr[]) {
        /**
         *         len_h = len(height)
         *         if len_h < 3:
         *             return 0
         *         stack, res = list(), 0
         *         for i in range(len_h):
         *             while stack and height[stack[-1]] < height[i]:
         *                 tmp = stack.pop()
         *                 if stack:
         *                     res += (min(height[i], height[stack[-1]]) - \
         *                             height[tmp])*(i - stack[-1] - 1)
         *             stack.append(i)
         */
        int len = arr.length;
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && arr[stack.get(stack.size() - 1)] < arr[i]) {
                int tmp = stack.pop();
                if (!stack.isEmpty()) {
                    int l = Math.min(arr[i], arr[stack.get(stack.size() - 1)]) - arr[tmp];
                    int r = i - stack.get(stack.size() - 1) - 1;
                    res += (l * r);
                }
            }
            stack.add(i);
        }
        return res;
    }
}
